# -*- coding: utf-8 -*-
"""
Created on Wed Dec 28 12:19:37 2022

@author: s'wan

数独 v2，按步 先发现解 再操作解，直至无解

1 确定值和候选同数组
2 返回每步的 推理逻辑及结果
3 推理与操作候选集分开
4 分散赋值，根据推理结果操作候选集之后，根据情况赋值，并重构候选集

"""
#%% import 
import numpy as np
from itertools import  combinations,product,permutations
from functools import cmp_to_key
from copy import deepcopy

#%% define

# algorithm
CELL_ONLY=1
DIGIT_ONLY=2
EXCLUDE_BLOCK=3
REPEL_BLOCK=4
EXCLUDE_RECT=5

#orient
DIR_ROW=1
DIR_COL=2
DIR_GONG=3

### 检查大九宫 是否出错
def is_error(arr):
    ### 检查子集 是否出错
    def _is_sub_error(sub):
        u,c = np.unique([candi for candi in sub if not isinstance(candi,set)],return_counts=True)
        return len((np.where(c[np.where(u>0)[0]]>1)[0]))>0
    
    for r in range(9):
        if _is_sub_error(arr[r]):
            return True

    for c in range(9):
        if _is_sub_error(arr[:,c]):
            return True

    for g in range(9):
        gr,gc = divmod(g,3) 
        if _is_sub_error(arr[gr*3:gr*3+3,gc*3:gc*3+3].reshape(-1)):
            return True
    return False


### 检查大九宫 是否完成
def is_done(arr):
    ### 检查子集 是否完成
    def _is_sub_done(sub):
        u = np.unique([candi for candi in sub if not isinstance(candi,set)])
        return u[0]==1 and u[-1]==9 and len(u)==9

    for row in arr:
        if not _is_sub_done(row) :
            return False
    for c in range(9):
        if not _is_sub_done(arr[:,c]) :
            return False
    for g in range(9):
        gr,gc = divmod(g,3)
        if not _is_sub_done(arr[gr*3:gr*3+3,gc*3:gc*3+3]):
            return False
        
    return True

### 计算 每格 候选集，返回 实际重构候选集的格数
def candidate_cell(arr):
    count = 0
    for r in range(9):
        for c in range(9):
            if isinstance(arr[r,c],set) or arr[r,c]==0: # 未决格
                diff = set(range(1,10)) # 差集
                diff = diff.difference([candi for candi in arr[r] if not isinstance(candi,set)])
                diff = diff.difference([candi for candi in arr[:,c] if not isinstance(candi,set)])
                gr,gc = int(r/3),int(c/3)
                diff = diff.difference([candi for candi in arr[gr*3:gr*3+3,gc*3:gc*3+3].reshape(-1) if not isinstance(candi,set)])
                if (isinstance(arr[r,c],set) and diff != arr[r,c]) or not isinstance(arr[r,c],set):
                    arr[r,c] = diff
                    count+=1
    return count

### 给唯一候选数的格 赋值,返回赋值格格数
def assign_cell(arr):
    count=0
    for r in range(9):
        for c in range(9):
            if isinstance(arr[r,c],set) and len(arr[r,c])==1:
                arr[r,c]=list(arr[r,c])[0]
                count+=1
    return count

###三链数(1,2,3,4,...) 删减法：子集（行列宫）的某3个格候仅候选某3个数，则其他格不能选此3数    
### n格仅候选n个数，但其他格可能也候选这n个数 #####
### 找到 有效的 即 退出
def cell_only_has(sub,no=3): 
    ### 候选个数 >1 且 <=no 的 格子集合
    check_cells=np.array([cell for cell in range(9) if isinstance(sub[cell],set)\
                          and len(sub[cell])>min(1,no-1) and len(sub[cell])<=no])
    
    ### N 个格子，no个一组，全部的组合
    for cell_comb in combinations(check_cells,no): # 格子的组合
        digit_union=set() # 格子组合的候选数字并集
        for cell in cell_comb:   
            digit_union.update(sub[cell]) # 格子组合候选数字并集

        if len(digit_union)==no: # 并集 大小 正好是 格子数
            for cell in range(9):
                if cell not in cell_comb and isinstance(sub[cell],set): # 其他格子 不能 候选这几个数
                    if len( digit_union.intersection(sub[cell]) )>0:
                        return [cell_comb,digit_union]
    return None

### 操作 cell_only_has 的结果
def cell_only_has_oper(sub,cells,digits):
    for cell in range(9):
        if cell not in cells and isinstance(sub[cell],set): # 其他格子 不能 候选这几个数
            sub[cell] = sub[cell].difference(digits)

### 隐性三链数(2,3,4,...)删减法：某3个数仅出现在子集（行列宫）的某3个格候选集，则此3格不能选其他数
### n个数仅被n格候选，但n格可能还候选别的数 #####
def digit_only_in(sub,no=3):
    ### 统计 数字候选次数
    dig_counts = np.array([sum([dig in candi for candi in sub if isinstance(candi,set)]) for dig in range(1,10)])
    
    ### 出现次数 大于1且小于等于no 的数  
    check_digits = np.where(list(map(lambda cnt: cnt > min(1,no-1) and cnt <= no,dig_counts)))[0] + 1
    
    if len(check_digits) < no: ### 至少要no个数
        return None
    
    # 存储 每个候选数 所在格的列表
    digit_cell = {dig:np.where([dig in candi if isinstance(candi,set) else False for candi in sub])[0] for dig in check_digits}
        
    ### N 个数字，3个组合，全部的组合数
    for dig_comb in combinations(check_digits,no):
        cell_union=set() # 组合各数出现位置的并集
        for dig in dig_comb:
            cell_union.update(digit_cell[dig])
        
        if len(cell_union)==no: # 出现的位置数正好是数字个数
            for cell in cell_union:
                if len( sub[cell].difference(dig_comb) ) > 0:
                    return [cell_union,dig_comb]
                
    return None

### 操作 隐性n(12,...)链数 结果
def digit_only_in_oper(sub,cells,digits):
    for cell in cells:
        sub[cell]=sub[cell].intersection(digits)

### 一次n链扫描
def only(arr,no,func):
    for r in range(9):
        sub = arr[r]
        res = func(sub,no)
        if res:
            return [DIR_ROW,r,res]
    
    for c in range(9):
        sub = arr[:,c]
        res = func(sub,no)
        if res:
            return [DIR_COL,c,res]
        
    for g in range(9):
        gr,gc = divmod(g,3) 
        sub = arr[gr*3:gr*3+3,gc*3:gc*3+3].reshape(-1)
        res = func(sub,no)
        if res:
            return [DIR_GONG,g,res]
        
    return None

### 操作n链的发现    
def only_oper(arr,orient,pos,res,func):
    if orient==DIR_ROW:
        sub=arr[pos]
        func(sub,*res)
        arr[pos] = sub    

    elif orient==DIR_COL:
        sub=arr[:,pos]
        func(sub,*res)
        arr[:,pos] = sub
        
    elif orient==DIR_GONG:
        gr,gc = divmod(pos,3) 
        sub = arr[gr*3:gr*3+3,gc*3:gc*3+3].reshape(-1)
        func(sub,*res)
        arr[gr*3:gr*3+3,gc*3:gc*3+3] = sub.reshape(3,3)

### 检查g之外其他宫的候选
def row_other_gong_has(arr,row,gong,dig):
    for g in set(range(3)).difference([gong]):
        for col in range(g*3,g*3+3): #所有同行格
            if isinstance(arr[row,col],set) and dig in arr[row,col]:
                return True
    return False
									
def col_other_gong_has(arr,col,gong,dig):
    for g in set(range(3)).difference([gong]):
        for row in range(g*3,g*3+3): #所有同列格
            if isinstance(arr[row,col],set) and dig in arr[row,col]:
                return True
    return False
   
### 3.区块摒除法  
### 若某行（列）块确定候选某数，则同行(列)其他行（列）块 不能 候选此数
def exclude_block(arr):
    for rs in range(0,9,3):
        # 统计3行的所有已填数
        digits= np.unique(list(filter(lambda dig: not isinstance(dig,set) and dig > 0,arr[rs:rs+3].reshape(-1))))
        # 遍历每个数
        for dig in digits:
            #   1 确定所在块的 宫位置
            pos=np.where(arr[rs:rs+3]==dig) # pos[0] 所在行,pos[1]所在列
            on_gongs = np.int8(np.floor(pos[1]/3)) # 所在宫
            
            # 要检查的 行 和 宫
            rows = list(set(list(range(rs,rs+3))).difference(pos[0]+rs))
            gongs = list(set(list(range(3))).difference(on_gongs))
            if len(gongs)==1: # 只需处理1宫
                if row_other_gong_has(arr,rows[0],gongs[0],dig):
                    return [DIR_ROW,rows[0],gongs[0],dig]
                
            elif len(gongs)==2: # 2宫，看有没有某宫可定：只有宫的某块填！！！！
                status = [(r,g,np.all(list(map(lambda dig:not isinstance(dig,set),arr[r,g*3:g*3+3]))))\
                          for r,g in product(rows,gongs)]
                filled = np.where(list(map(lambda t: t[2],status)))[0] ### 已填的块 
                for i in filled:
                    other_same_gong = np.where(list(map(lambda t: t[1]==status[i][1] and t[0]!=status[i][0],status)))[0][0]
                    if row_other_gong_has(arr,status[other_same_gong][0],status[other_same_gong][1],dig):
                        return [DIR_ROW,status[other_same_gong][0],status[other_same_gong][1],dig]
                    else:
                        other_same_line = np.where(list(map(lambda t: t[1]!=status[i][1] and t[0]==status[i][0],status)))[0][0]
                        if row_other_gong_has(arr,status[other_same_line][0],status[other_same_line][1],dig):
                            return [DIR_ROW,status[other_same_line][0],status[other_same_line][1],dig]
                    
    for cs in range(0,9,3):
        # 统计3列的所有已填数
        digits= np.unique(list(filter(lambda dig: not isinstance(dig,set) and dig > 0, arr[:,cs:cs+3].reshape(-1))))
        # 遍历每个数
        for dig in digits:
            #   1 确定所在块的 宫位置
            pos=np.where(arr[:,cs:cs+3]==dig) # pos[0] 所在行,pos[1]所在列
            on_gongs = np.int8(np.floor(pos[0]/3)) # 所在宫
            
            # 要检查的 列 和 宫
            cols = list(set(list(range(cs,cs+3))).difference(pos[1]+cs))
            gongs = list(set(list(range(3))).difference(on_gongs))
            if len(gongs)==1: # 只需处理1宫
                if col_other_gong_has(arr,cols[0],gongs[0],dig):
                    return [DIR_COL,cols[0],gongs[0],dig]
                
            elif len(gongs)==2: # 2宫，看有没有某宫可定：只有宫的某块填！！！！
                status = [(c,g,np.all(list(map(lambda dig: not isinstance(dig,set),arr[g*3:g*3+3,c]))))\
                          for c,g in product(cols,gongs)]
                filled = np.where(list(map(lambda t: t[2],status)))[0] ### 已填的块 
                for i in filled:
                    other_same_gong = np.where(list(map(lambda t: t[1]==status[i][1] and t[0]!=status[i][0],status)))[0][0]
                    if col_other_gong_has(arr,status[other_same_gong][0],status[other_same_gong][1],dig):
                        return [DIR_COL,status[other_same_gong][0],status[other_same_gong][1],dig]
                    
                    else:
                        other_same_line = np.where(list(map(lambda t: t[1]!=status[i][1] and t[0]==status[i][0],status)))[0][0]
                        if col_other_gong_has(arr,status[other_same_line][0],status[other_same_line][1],dig):
                            return [DIR_COL,status[other_same_line][0],status[other_same_line][1],dig]
    return None
                    
'''
块排斥法：某数只被宫内某行(列)候选，则该行其他宫不能候选此数
'''

def repel_block(arr):
    def _union_set(sub):
        digit_union=set()
        for candi in sub:
            if isinstance(candi,set):
                digit_union.update(candi)
        return digit_union
    
    for gr in range(3):
        for gc in range(3):
            row_candi_unions = [_union_set(arr[row,gc*3:gc*3+3]) for row in range(gr*3,gr*3+3)]
            diff_union = {i+gr*3:row_candi_unions[i].difference(row_candi_unions[j].union(row_candi_unions[k]))\
                          for i,j,k in permutations(range(3))}
            for row,diff in diff_union.items():
                if len(diff)==1 and row_other_gong_has(arr,row,gc,list(diff)[0]):
                    return [DIR_ROW,row,gc,list(diff)[0]]
                    
            col_candi_unions = [_union_set(arr[gr*3:gr*3+3,col]) for col in range(gc*3,gc*3+3)]
            diff_union = {i+gc*3:col_candi_unions[i].difference(col_candi_unions[j].union(col_candi_unions[k]))\
                          for i,j,k in permutations(range(3))}
            for col,diff in diff_union.items():
                if len(diff)==1 and col_other_gong_has(arr,col,gr,list(diff)[0]):
                    return [DIR_COL,col,gr,list(diff)[0]]
                
    return None
    
### 擦g之外其他宫的候选
def block_oper(arr,orient,unit,gong,digit):
    def _erase_row_candidate(arr,row,gong,digit):
        for g in set(range(3)).difference([gong]):
            for col in range(g*3,g*3+3): #所有同行格
                if isinstance(arr[row,col],set):
                    arr[row,col]=arr[row,col].difference([digit]) # val不再候选
                
    def _erase_col_candidate(may,col,gong,digit):
        for g in set(range(3)).difference([gong]):
            for row in range(g*3,g*3+3): #所有同列格
                if isinstance(arr[row,col],set):
                    arr[row,col]=arr[row,col].difference([digit]) # val不再候选
    
    if orient==DIR_ROW:
        _erase_row_candidate(arr,unit,gong,digit)
    elif orient==DIR_COL:
        _erase_col_candidate(arr,unit,gong,digit)


### 5.矩形摒除法（矩形顶点删减法）
### 某两列（行）仅在相同行（列）可取某数，则这两行（列）其他格不能取此数
### 三链列（行）删减法 --矩形删减法扩展
  
def exclude_rectangle(arr,no=2):
    def intersection(k_kv,ks):
        its=set(range(9))
        for k in ks:
            its = its.intersection(k_kv[k].keys())
        return its
    
    def set_equal(k_kv,rows,dig):
        for row in rows[1:]:
            if k_kv[rows[0]][dig] != k_kv[row][dig]:
                return False
        return True

    ## 计算各行 被选2次的数字所在位置
    row_dig_cells=[]
    for row in range(9):
        # 统计 数字 <-> 所在候选格
        dig_cells={dig:{col for col in range(9) if isinstance(arr[row,col],set)  and dig in arr[row,col]} \
              for dig in  range(1,10)}
        row_dig_cells.append({dig:cells for dig,cells in dig_cells.items() if len(cells)==no})
    row_dig_cells={row:dig_cells for row,dig_cells in enumerate(row_dig_cells) if len(dig_cells)>0}
    
    for rows in combinations(row_dig_cells, no):
        jiaoji = intersection(row_dig_cells,rows)
        for dig in jiaoji:
            if set_equal(row_dig_cells,rows,dig):
                ### 从两列的其他候选 删除 该值
                for col in row_dig_cells[rows[0]][dig]:
                    for row in range(9):
                        if row not in rows and isinstance(arr[row,col],set) and dig in arr[row,col]:
                            return [DIR_ROW,rows,row_dig_cells[rows[0]][dig],dig]

    ## 计算各列 被选2次的数字所在位置
    col_dig_cells=[]
    for col in range(9):
        dig_cells={dig:{row for row in range(9) if isinstance(arr[row,col],set)  and dig in arr[row,col]} \
              for dig in  range(1,10)}
        col_dig_cells.append({dig:cells for dig,cells in dig_cells.items() if len(cells)==no})
    col_dig_cells={col:dig_cells for col,dig_cells in enumerate(col_dig_cells) if len(dig_cells)>0}
    
    for cols in combinations(col_dig_cells, no):
        jiaoji = intersection(col_dig_cells,cols)
        for dig in jiaoji:
            if set_equal(col_dig_cells,cols,dig):
                ### 从两列的其他候选 删除 该值
                for row in col_dig_cells[cols[0]][dig]:
                    for col in range(9):
                        if col not in cols and isinstance(arr[row,col],set) and dig in arr[row,col]:
                            return [DIR_COL,cols,col_dig_cells[cols[0]][dig],dig]
    return None

def rectangle_oper(arr,orient,ones,others,dig):
    if orient==DIR_ROW:
        for col in others:
            for row in range(9):
                if row not in ones and isinstance(arr[row,col],set):
                    arr[row,col]=arr[row,col].difference([dig])
    elif orient==DIR_COL:
        for row in others:
            for col in range(9):
                if col not in ones and isinstance(arr[row,col],set):
                    arr[row,col]=arr[row,col].difference([dig])
ALG_STACK={
    DIGIT_ONLY:(digit_only_in,digit_only_in_oper),
    CELL_ONLY:(cell_only_has,cell_only_has_oper),
    EXCLUDE_BLOCK:(exclude_block,block_oper),
    REPEL_BLOCK:(repel_block,block_oper),
    EXCLUDE_RECT:(exclude_rectangle,rectangle_oper),
}

def find_step(arr):
    for n,alg in product([1,2,3,4,5,6],[DIGIT_ONLY,CELL_ONLY]):
        while True:
            res = only(arr, n, ALG_STACK[alg][0])
            if res:
                return [alg,res]
            else:
                break

    for alg in [REPEL_BLOCK,EXCLUDE_BLOCK]:
        while True:
            res = ALG_STACK[alg][0](arr)
            if res:
                return [alg,res]
            else:
                break

    for n in [2,3,4]:
        while True:
            res = ALG_STACK[EXCLUDE_RECT][0](arr, n)
            if res:
                return [EXCLUDE_RECT,res]
            else:
                break

    return None

def oper_step(arr,res):
    if res[0] in [CELL_ONLY,DIGIT_ONLY]:
        only_oper(arr, *res[1],ALG_STACK[res[0]][1])
    else:
        ALG_STACK[res[0]][1](arr,*res[1])
    '''if res[0]==CELL_ONLY:
        only_oper(arr, *res[1],cell_only_has_oper)
    elif res[0]==DIGIT_ONLY:
        only_oper(arr, *res[1],digit_only_in_oper)
    elif res[0]==EXCLUDE_BLOCK or res[0]==REPEL_BLOCK:
        block_oper(arr, *res[1])
    elif res[0]==EXCLUDE_RECT:
        rectangle_oper(arr, *res[1])'''
        
### 总搜寻
def solve(arr,verbose=True):
    candidate_cell(arr)
    while True:
        res = find_step(arr)
        if res:
            if verbose:
                print(res)
            oper_step(arr,res)
        else:
            break
    assign_cell(arr)
    return is_done(arr)


###------------------------------------------
# 找到不定格性 最少 的组（行列宫）及最少候选的格

def try_suppose(arr):
    '''def _min_min(sub):
        candi_cnt,min_dig_cnt,min_cell = 0,10,-1 # 候选个数 和 候选最少的数字个数
        for cell in range(9):
            if isinstance(sub[cell], set):
                candi_cnt+=1
                if len(sub[cell]) < min_dig_cnt:
                    min_dig_cnt = len(sub[cell])
                    min_cell = cell
        return candi_cnt,min_dig_cnt,min_cell
    
    def _find_minimum(arr):        
        res=[]
        for r in range(9):
            res.append([(1,r),_min_min(arr[r])])
        for c in range(9):
            res.append([(2,c),_min_min(arr[r])])
        for g in range(9):
            gr,gc = divmod(g,3) 
            res.append([(3,g),_min_min(arr[gr*3:gr*3+3,gc*3:gc*3+3].reshape(-1))])
            
        return sorted(res,key=cmp_to_key(lambda i1,i2 : i1[1][1]-i2[1][1] if i1[1][0]==i2[1][0] else i1[1][0]-i2[1][0]))

    def _get_coord(t):
        if t[0][0]==1:
            return t[0][1],t[1][2]
        if t[0][0]==2:
            return t[1][2],t[0][1]
        gr,gc = divmod(t[0][1],3)
        ir,ic = divmod(t[1][2],3)
        return gr*3+ir,gc*3+ic
    
    tries = _find_minimum(arr)
    for t in tries:
        print(t)
        r,c = _get_coord(t)
        for dig in arr[r,c]:
            dummy = deepcopy(arr)
            dummy[r,c]=dig
            if solve(dummy,False):
                return dummy'''
    cell_dig_cnt = [(r,c,len(arr[r,c])) for r,c in product(range(9),range(9)) if isinstance(arr[r,c],set)]
    cell_dig_cnt = sorted(cell_dig_cnt,key=cmp_to_key(lambda i1,i2 : i1[2]-i2[2]))
    for r,c,_ in cell_dig_cnt:
        print(r,c)
        for dig in arr[r,c]:
            dummy = deepcopy(arr)
            dummy[r,c]=dig
            if solve(dummy,False):
                return dummy


#%% usage

if not solve(arr):
    arr = try_suppose(arr)

is_error(arr)
is_done(arr)

np.array([[len(arr[r,c]) if isinstance(arr[r,c],set) else None  for c in range(9)] for r in range(9)])
#各数字 解决个数
u,c = np.unique([dig for dig in arr.reshape(-1) if not isinstance(dig,set)],return_counts=True)
